public class LinkedList<T> {

    private class Node{
        private T t;
        private Node next;

        public Node(T t,Node next){
            this.t = t;
            this.next = next;
        }

        public Node(T t){
            this(t,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString(){
            return t.toString();
        }
    }

    private int size;
    private Node dummyHead;

    public LinkedList(){
        this.size = 0;
        dummyHead = new Node(null,null);
    }

    //获取链表中的元素个数
    public int getSize(){
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    //在链表的index位置添加新的元素
    //在链表中这不是一个常用操作
    public void add(int index,T t){
        if(index <0 || index > size){
            throw new IllegalArgumentException("add Failed,Illegal index");
        }

        Node prev = dummyHead;
        for(int i=0;i<index;i++){
            prev = prev.next;
        }
//        Node node = new Node(t);
//        node.next = prev.next;
//        prev.next = node;
            //精简为：
        prev.next = new Node(t,prev.next);
        size ++;
    }

    //在链表头添加新的元素
    public void addFirst(T t){
        add(0,t);
    }

    //在链表末尾添加新元素
    public void addLast(T t){
        add(size,t);
    }

    //获取指定索引位置的元素
    //在链表中这不是一个常用操作
    public T get(int index){
        if(index<0 || index >= size){
            throw new IllegalArgumentException("get Faild,Illegal index");
        }
        Node cur = dummyHead.next;
        for(int i = 0;i<index;i++){
            cur = cur.next;
        }
        return cur.t;
    }

    //获取链表中的第一个元素
    public T getFirst(){
        return get(0);
    }

    //获取链表中的最后一个元素
    public T getLast(){
        return get(size - 1);
    }

    //修改指定索引位置的元素
    public void set(int index,T t){
        if(index<0 || index >= size){
            throw new IllegalArgumentException("get Faild,Illegal index");
        }
        Node cur = dummyHead.next;
        for(int i=0;i<index;i++){
            cur = cur.next;
        }
        cur.t = t;
    }

    //判断链表中是否存在某元素
    public boolean contains(T t){
        Node cur = dummyHead.next;
        while (cur != null){
            if(cur.t.equals(t)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除链表中指定索引位置的元素
    public T remove(int index){
        if(index<0 || index >=size){
            throw  new IllegalArgumentException("remove Failed,index is Illegal");
        }

        Node prevNode = dummyHead;
        for(int i =0;i<index;i++){
            prevNode = prevNode.next;
        }

        Node delNode = prevNode.next;
        prevNode.next = delNode.next;
        delNode.next = null;
        size --;

        return delNode.t;

    }

    //删除链表中的第一个元素
    public T removeFirst(){
        return remove(0);
    }

    //删除链表中最后一个元素
    public T removeLast(){
        return remove(size-1);
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

//        Node cur = dummyHead.next;
//        while (cur != null){
//            res.append(cur.t+"->");
//            cur = cur.next;
//        }
    //精简为：
        for(Node cur = dummyHead.next;cur != null;cur=cur.next){
            res.append(cur.t+"->");
        }
        res.append("NULL");
        return res.toString();

    }
}
